package com.pointstar.dp.sort;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

/**
 * 南软2003T2
 * 直接插入排序
 * 机器配置信息：内存(16G)、CPU(i7-7700、4核)
 * 待排序数量    耗时（单位：s）
 * 10          0
 * 100         0.001
 * 1000        0.01
 * 10000       0.065
 * 20000       0.253
 * 30000       0.531
 * 40000       0.857
 * 50000       1.334
 * 100000      4.933
 * 1000000     628.598
 *
 * @author 禾绪
 */
public class InsertionSort {

    public static void main(String[] args) {

        List<Integer> unsortedList = new ArrayList<>();
        IntStream.range(1, 10000).forEach(unsortedList::add);
        System.out.println("未排序：" + unsortedList.toString());
        sortWithInsertion(unsortedList);
        System.out.println("已排序：" + unsortedList.toString());
    }

    /**
     * 每次将一个待排序的数据逐一和已排序的数据比较，直到找到合适的插入位置。
     *
     * @param unsortedList 待排序列表
     */
    private static void sortWithInsertion(List<Integer> unsortedList) {

        long startTime = System.currentTimeMillis();
        int temp;
        //第一个数默认有序，大循环从第二个数开始遍历
        for (int i = 1; i < unsortedList.size(); i++) {

            //当前最新待排序数赋值给哨兵
            temp = unsortedList.get(i);
            int j = i - 1;
            //从后往前依次遍历已排序的数组，若满足交换条件则交换
            //交换条件根据排序类型确定：若升序，则已排序数大于哨兵则交换；若降序，则已排序数小于哨兵则交换。
            for (; j >= 0 && unsortedList.get(j) < temp; j--) {

                unsortedList.set(j + 1, unsortedList.get(j));
            }
            //找到最新待排序数的插入位置并插入
            unsortedList.set(j + 1, temp);
        }
        System.out.println("执行耗时：" + (System.currentTimeMillis() - startTime) / 1000f + "s");
    }

}
